package leetcode_600;

/**
 *@author 周杨
 *NonNegativeIntegersWithoutConsecutiveOnes_600 给定一个n 判断小于等于n的非负整数二进制有没有连续1
 *describe:用动态规划 AC 34%
 *see:https://www.cnblogs.com/grandyang/p/6959585.html
 *2018年9月18日 下午3:31:09
 */
public class NonNegativeIntegersWithoutConsecutiveOnes_600 {
	public static void main(String[] args) {
		NonNegativeIntegersWithoutConsecutiveOnes_600 test=new NonNegativeIntegersWithoutConsecutiveOnes_600();
		System.out.println(test.findIntegers(100000000));
	}
	
	
	public int findIntegers(int num) {
		int cnt = 0, n = num;
	    String t = "";
	    while (n > 0) {
	       ++cnt;
	       t += ((n & 1)==1) ? "1" : "0"; 
	     n >>= 1;
	    }
		int dp0[]=new int[cnt];
		int dp1[]=new int[cnt];
		dp0[0]=1;
		dp1[0]=1;
		for(int i=1;i<cnt;++i) {
			dp0[i]=dp0[i-1]+dp1[i-1];
			dp1[i]=dp0[i-1];
		}
		int res=dp0[cnt-1]+dp1[cnt-1];
		char chars[]=t.toCharArray();
        for(int i=cnt-2;i>=0;--i) {
        	if(chars[i]=='1'&&chars[i+1]=='1')
        		break;//终止找多余的
        	if(chars[i]=='0'&&chars[i+1]=='0')
        		res-=dp1[i];
        }
        return res;
    }
	
	/**
	 * describe:问小于num的二进制不出现连续1的个数
	 * 2018年9月18日 下午12:22:22
	 */
	public int findIntegers1(int num) {
		int res=0;
        for(int i=0;i<=num;++i) {
        	if(judge(Integer.toBinaryString(i)))
        		++res;
        }
        return res;
    }
	
	public boolean judge(String s) {
		if(s.length()<=1)
			return true;
		char []chars=s.toCharArray();
		for(int i=1;i<chars.length;++i) {
			if(chars[i]=='1'&&chars[i-1]=='1')
				return false;
		}
		return true;
	}
}
